package graphic;

import java.util.*;

/**
 * @author pengfei.hpf
 * @date 2020/2/28
 * @verdion 1.0.0
 * 对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。
 *
 * 格式
 *
 * 该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。
 *
 * 你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。
 *
 * 示例 1:
 *
 * 输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
 *
 *         0
 *         |
 *         1
 *        / \
 *       2   3
 *
 * 输出: [1]
 * 示例 2:
 *
 * 输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
 *
 *      0  1  2
 *       \ | /
 *         3
 *         |
 *         4
 *         |
 *         5
 *
 * 输出: [3, 4]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-height-trees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FindMinHeightTrees {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new LinkedList<>();

        //if edges.length == 0?
        if(n == 0 || edges == null){
            return res;
        }
        if(n == 1){
            res.add(0);
            return res;
        }
        int[] degree = new int[n];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i = 0; i < edges.length; i ++){
            map.computeIfAbsent(edges[i][0], x-> new ArrayList<>()).add(edges[i][1]);
            map.computeIfAbsent(edges[i][1], x-> new ArrayList<>()).add(edges[i][0]);
            degree[edges[i][0]] ++;
            degree[edges[i][1]] ++;
        }
        Queue<Integer> queue = new LinkedList<>();

        for(int i = 0; i < n; i ++){
            if(degree[i] == 1){
                queue.add(i);
                degree[i]--;
            }
        }
        Set<Integer> lastOne = null;
        while(!queue.isEmpty()){
            lastOne = new HashSet(queue);
            int size = queue.size();
            for(int i = 0; i < size; i++){
                int c = queue.poll();
                for(int nei: map.get(c)){
                    degree[nei] --;
                    if(degree[nei] == 1){
                        queue.add(nei);
                    }
                }
            }
        }
        res.addAll(lastOne);
        return res;
    }
}
